package org.example.myleet.p583;

public class Solution {
    /**
     * 思路：动态规划，题目求删除字符个数，可以转换成求两个单词的最长公共子序列，然后就可以知道两个单词需要删除的字符的数量
     */
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        //记录两个字符能够匹配的最长公共子序列的长度，两个word的下标从1开始算
        int[][] dp = new int[n1 + 1][n2 + 1];
        for (int i = 0; i < n1; ++i) {
            char c1 = word1.charAt(i);
            for (int j = 0; j < n2; ++j) {
                char c2 = word2.charAt(j);
                //左上角的匹配数量，左上角指word1[i]、word2[j]匹配的位置
                int newDp = dp[i][j];
                if (c1 == c2) {
                    //字符匹配，则可以在左上角的匹配数量基础上+1
                    ++newDp;
                }
                //递推公式，dp[i + 1][j + 1]取word1[i-1]-word2[j]、word1[i]-word2[j-1]、word1[i-1]-word2[j-1]匹配最长的数量
                dp[i + 1][j + 1] = Math.max(Math.max(dp[i][j + 1], dp[i + 1][j]), newDp);
            }
        }
        int longestCommonSubSeqLen = dp[n1][n2];
        return n1 - longestCommonSubSeqLen + (n2 - longestCommonSubSeqLen);
    }
}
